Instructions for the assignment¶

• This assignment consists of both programming and theory questions.

• Unless a theory question explicitly states that no work is required to be shown, you must provide an explanation, justification, or calculation for your answer.

• To switch between cell for code and for markdown, see the menu -> Cell -> Cell Type

• You can directly type Latex equations into markdown cells.

• If a question requires a picture, you could use this syntax <img src="" style="width: 300px;"/> to include them within your ipython notebook.

• Your write up must be submitted in PDF form. You may use either Latex, markdown, or any word processing software. We will **NOT** accept handwritten work. Make sure that your work is formatted correctly, for example submit $\sum_{i=0} x_i$ instead of \text{sum_{i=0} x_i}

• When submitting the non-programming part of your assignment, you must correctly map pages of your PDF to each question/subquestion to reflect where they appear. **Improperly mapped questions may not be graded correctly and/or will result in point deductions for the error.**
• All assignments should be done individually, and each student must write up and submit their own answers.
• Graduate Students: You are required to complete any sections marked as Bonus for Undergrads

Using the autograder¶

• Grads will find three assignments on Gradescope that correspond to HW3: "Assignment 3 Programming", "Assignment 3 - Non-programming" and "Assignment 3 Programming - Bonus for all". Undergrads will find an additional assignment called "Assignment 3 Programming - Bonus for Undergrads".

• You will submit your code for the autograder in the Assignment 3 Programming sections. Please refer to the Deliverables and Point Distribution section for what parts are considered required, bonus for undergrads, and bonus for all.

• We provided you different .py files and we added libraries in those files please DO NOT remove those lines and add your code after those lines. Note that these are the only allowed libraries that you can use for the homework.

• You are allowed to make as many submissions until the deadline as you like. Additionally, note that the autograder tests each function separately, therefore it can serve as a useful tool to help you debug your code if you are not sure of what part of your implementation might have an issue.

• For the "Assignment 3 - Non-programming" part, you will need to submit to Gradescope a PDF copy of your Jupyter Notebook with the cells ran. See this EdStem Post for multiple ways on to convert your .ipynb into a .pdf file. Please refer to the Deliverables and Point Distribution section for an outline of the non-programming questions.

• When submitting to Gradescope, please make sure to mark the page(s) corresponding to each problem/sub-problem. The pages in the PDF should be of size 8.5" x 11", otherwise there may be a deduction in points for extra long sheets.

Using the local tests ¶

• For some of the programming questions we have included a local test using a small toy dataset to aid in debugging. The local test sample data and outputs are stored in .py files in the local_tests_folder. The actual local tests are stored in localtests.py.
• There are no points associated with passing or failing the local tests, you must still pass the autograder to get points.
• It is possible to fail the local test and pass the autograder since the autograder has a certain allowed error tolerance while the local test allowed error may be smaller. Likewise, passing the local tests does not guarantee passing the autograder.
• You do not need to pass both local and autograder tests to get points, passing the Gradescope autograder is sufficient for credit.
• It might be helpful to comment out the tests for functions that have not been completed yet.
• It is recommended to test the functions as it gets completed instead of completing the whole class and then testing. This may help in isolating errors. Do not solely rely on the local tests, continue to test on the autograder regularly as well.

Deliverables and Points Distribution¶

Q1: Image Compression [30pts]¶

Deliverables: imgcompression.py and printed results¶

• 1.1 Image Compression [20 pts] - programming

  • svd [4pts]

  • compress [4pts]

  • rebuild_svd [4pts]

  • compression_ratio [4pts]

  • recovered_variance_proportion [4pts]

• 1.2 Black and White [5 pts] non-programming

• 1.3 Color Image [5 pts] non-programming

Q2: Understanding PCA [20pts]¶

Deliverables: pca.py and written portion¶

• 2.1 PCA Implementation [10 pts] - programming

  • fit [5pts]

  • transform [2pts]

  • transform_rv [3pts]

• 2.2 Visualize [5 pts] programming and non-programming

• 2.3 PCA Reduced Facemask Dataset Analysis [5 pts] non-programming

• 2.4 PCA Exploration [0 pts]

Q3: Regression and Regularization [80pts: 50pts + 20pts Bonus for Undergrads + 10pts Bonus for All]¶

Deliverables: regression.py and Written portion¶

• 3.1 Regression and Regularization Implementations [50pts: 30pts + 20pts Bonus for Undergrad] - programming

  • RMSE [5pts]

  • Construct Poly Features 1D [2pts]

  • Construct Poly Features 2D [3pts]

  • Prediction [5pts]

  • Linear Fit Closed Form [5pts]

  • Ridge Fit Closed Form [5pts]

  • Cross Validation [5pts]

  • Linear Gradient Descent [5pts] Bonus for Undergrad

  • Linear Stochastic Gradient Descent [5pts] Bonus for Undergrad

  • Ridge Gradient Descent [5pts] Bonus for Undergrad

  • Ridge Stochastic Gradient Descent [5pts] Bonus for Undergrad

• 3.2 About RMSE [3 pts] non-programming

• 3.3 Testing: General Functions and Linear Regression [5 pts] non-programming

• 3.4 Testing: Ridge Regression [5 pts] non-programming

• 3.5 Cross Validation [7 pts] non-programming

• 3.6 Noisy Input Samples in Linear Regression [10 pts] non-programming BONUS FOR ALL

Q4: Naive Bayes and Logistic Regression [35pts]¶

Deliverables: logistic_regression.py and Written portion¶

• 4.1 Llama Breed Problem using Naive Bayes [5 pts] non-programming

• 4.2 News Data Sentiment Classification Using Logistic Regression [30 pts] - programming

  • sigmoid [2 pts]

  • bias_augment [3 pts]

  • predict_probs [5 pts]

  • predict_labels [2 pts]

  • loss [3 pts]

  • gradient [3 pts]

  • accuracy [2 pts]

  • evaluate [5 pts]

  • fit [5 pts]

Q5: Noise in PCA and Linear Regression [15pts]¶

Deliverables: Written portion¶

• 5.1 Slope Functions [5 pts] non-programming

• 5.2 Error in Y and Error in X and Y [5 pts] non-programming

• 5.3 Analysis [5 pts] non-programming

Q6: Feature Reduction.py [25pts Bonus for All]¶

Deliverables: feature_reduction.py and Written portion¶

• 6.1 Feature Reduction [18 pts] - programming

  • forward_selection [9pts]

  • backward_elimination [9pts]

• 6.2 Feature Selection - Discussion [7 pts] non-programming

Q7: Movie Recommendation with SVD [10pts Bonus for All]¶

Deliverables: svd_recommender.py and Written portion¶

• 7.1 SVD Recommender

  • recommender_svd [5pts]

  • predict [5pts]

• 7.2 Visualize Movie Vectors [0pts]

0 Set up¶

This notebook is tested under python 3. ., and the corresponding packages can be downloaded from miniconda. You may also want to get yourself familiar with several packages:

• jupyter notebook
• numpy
• matplotlib
• sklearn

There is also a VS Code and Anaconda Setup Tutorial on Ed under the "Links" category

Please implement the functions that have raise NotImplementedError, and after you finish the coding, please delete or comment out raise NotImplementedError.

Library imports¶

Q1: Image Compression [30 pts] **[P]** | **[W]**¶

Load images data and plot¶

1.1 Image compression [20pts] **[P]**¶

SVD is a dimensionality reduction technique that allows us to compress images by throwing away the least important information.

Higher singular values capture greater variance and, thus, capture greater information from the corresponding singular vector. To perform image compression, apply SVD on each matrix and get rid of the small singular values to compress the image. The loss of information through this process is negligible, and the difference between the images can be hardly spotted.

For example, the proportion of variance captured by the first component is $$\frac{\sigma_1^2}{\sum_{i=1}^n \sigma_i^2}$$ where $\sigma_i$ is the $i^{th}$ singular value.

In the imgcompression.py file, complete the following functions:

• svd: You may use np.linalg.svd in this function, and although the function defaults this parameter to true, you may explicitly set full_matrices=True using the optional full_matrices parameter. Hint 2 may be useful.
• compress
• rebuild_svd
• compression_ratio: Hint 1 may be useful
• recovered_variance_proportion: Hint 1 may be useful

HINT 1: http://timbaumann.info/svd-image-compression-demo/ is a useful article on image compression and compression ratio. You may find this article useful for implementing the functions compression_ratio and recovered_variance_proportion

HINT 2: If you have never used np.linalg.svd, it might be helpful to read Numpy's SVD documentation and note the particularities of the $V$ matrix and that it is returned already transposed.

HINT 3: The shape of $S$ resulting from SVD may change depending on if N > D, N < D, or N = D. Therefore, when checking the shape of $S$, note that min(N,D) means the value should be equal to whichever is lower between N and D.

1.1.1 Local Tests for Image Compression Black and White Case [No Points]¶

You may test your implementation of the functions contained in imgcompression.py in the cell below. Feel free to comment out tests for functions that have not been completed yet. See Using the Local Tests for more details.

1.1.2 Local Tests for Image Compression Color Case [No Points]¶

You may test your implementation of the functions contained in imgcompression.py in the cell below. Feel free to comment out tests for functions that have not been completed yet. See Using the Local Tests for more details.

1.2.1 Black and white [5 pts] **[W]**¶

This question will use your implementation of the functions from Q1.1 to generate a set of images compressed to different degrees. You can simply run the below cell without making any changes to it, assuming you have implemented the functions in Q1.1.

Make sure these images are displayed when submitting the PDF version of the Juypter notebook as part of the non-programming submission of this assignment.

1.2.2 Black and White Compression Savings [No Points]¶

This question will use your implementation of the functions from Q1.1 to compare the number of bytes required to represent the SVD decomposition for the original image to the compressed image using different degrees of compression. You can simply run the below cell without making any changes to it, assuming you have implemented the functions in Q1.1.

Running this cell is primarily for your own understanding of the compression process.

1.3.1 Color image [5 pts] **[W]**¶

This section will use your implementation of the functions from Q1.1 to generate a set of images compressed to different degrees. You can simply run the below cell without making any changes to it, assuming you have implemented the functions in Q1.1.

Make sure these images are displayed when submitting the PDF version of the Juypter notebook as part of the non-programming submission of this assignment.

NOTE: You might get warning "Clipping input data to the valid range for imshow with RGB data ([0..1] for floats or [0..255] for integers)." This warning is acceptable since some of the pixels may go above 1.0 while rebuilding. You should see similar images to original even with such clipping.

HINT 1: Make sure your implementation of recovered_variance_proportion returns an array of 3 floats for a color image.
HINT 2: Try performing SVD on the individual color channels and then stack the individual channel $U$, $S$, $V$ matrices.
HINT 3: You may need separate implementations for a color or grayscale image in the same function.

1.3.2 Color Compression Savings [No Points]¶

This question will use your implementation of the functions from Q1.1 to compare the number of bytes required to represent the SVD decomposition for the original image to the compressed image using different degrees of compression. You can simply run the below cell without making any changes to it, assuming you have implemented the functions in Q1.1.

Running this cell is primarily for your own understanding of the compression process.

Q2: Understanding PCA [20 pts] **[P]** | **[W]**¶

Principal Component Analysis (PCA) is another dimensionality reduction technique that reduces dimensions by eliminating small variance eigenvalues and their vectors. With PCA, we center the data first by subtracting the mean of each feature. Each singular value tells us how much of the variance of a matrix (e.g. image) is captured in each component. In this problem, we will investigate how PCA can be used to improve features for regression and classification tasks and how the data itself affects the behavior of PCA.

Here we will implement PCA using Singular Value Decomposition (SVD). Recall from class that in PCA, we project the original matrix $X$ into new components, each one corresponding to an eigenvector of the covariance matrix $X^T X$. SVD decomposes $X$ into three matrices $U$, $S$ and $V^T$. This also leads us a decomposition of the covariance matrix as: $$X^TX = (USV^T)^TUSV^T = (VS^TU^T)USV^T = V S^2 V^T$$

This means two important things for us:

• The matrix $V^T$, often referred to as the right singular vectors of $X$, is equivalent to the eigenvectors of $X^TX$.
• $S^2$ is equivalent to the eigenvalues of $X^TX$.

So the first $n$-principal components are obtained by projecting $X$ by the first $n$ vectors from $V^T$. Similarly, $S^2$ gives a measure of the variance retained.

2.1 Implementation [10 pts] **[P]**¶

Implement PCA. In the pca.py file, complete the following functions:

• fit: You may use np.linalg.svd. Set full_matrices=False. Hint 1 may be useful.
• transform
• transform_rv: You may find np.cumsum helpful for this function.

Assume a dataset is composed of N datapoints, each of which has D features with D < N. The dimension of our data would be D. However, it is possible that many of these dimensions contain redundant information. Each feature explains part of the variance in our dataset, and some features may explain more variance than others.

HINT 1: Make sure you remember to first center your data by subtracting the mean of each feature.

2.1.1 Local Tests for PCA [No Points]¶

You may test your implementation of the functions contained in pca.py in the cell below. Feel free to comment out tests for functions that have not been completed yet. See Using the Local Tests for more details.

2.2 Visualize [5 pts] **[W]**¶

PCA is used to transform multivariate data tables into smaller sets so as to observe the hidden trends and variations in the data. It can also be used as a feature extractor for images. Here you will visualize two datasets using PCA, first is the iris dataset and then a dataset of masked and unmasked images.

In the pca.py, complete the following function:

• visualize: Use your implementation of PCA and reduce the datasets such that they contain only two features. Using Matplotlib's Pyplot, create 2-D scatter plots of the data points using these features. Make sure to differentiate the data points according to their true labels using color.

The datasets have already been loaded for you in the subsequent cells.

NOTE: Here, we won't be testing for accuracy. Even with correct implementations of PCA, the accuracy can differ from the TA solution. That is fine as long as the visualizations come out similar.

Iris Dataset¶

2.3 PCA Reduced Facemask Dataset Analysis [5 pts] **[W]**¶

Facemask Dataset¶

The masked and unmasked dataset is made up of grayscale images of human faces facing forward. Half of these images are faces that are completely unmasked, and the remaining images show half of the face covered with an artificially generated face mask. The images have already been preprocessed, they are also reduced to a small size of 64x64 pixels and then reshaped into a feature vector of 4096 pixels. Below is a sample of some of the images in the dataset.

What do you think of this 2 dimensional plot, knowing that the original dataset was originally a set of flattened image vectors that had 4096 pixels/features?.

1. Look at the 2-dimensional plot above. If the facemask dataset that has been reduced to 2 features was fed into a classifier, do you think the classifier would produce high accuracy or low accuracy in comparison to the original dataset which had 4096 pixels/features? Why? You can refer to the 2D visualization made above (One or two sentences will suffice for this question) (3 pts)

   Answer ...

   The classifier will end up with a lower accuracy because it cannot specify the main patterns and variations in the dataset due to a removal of features

1. Assuming an equal rate of accuracy, what do you think is the main advantage in feeding a classifier a dataset with 2 features vs a dataset with 4096 features? (One sentence will suffice for this question.) (2 pts)

   Answer ...

   Computational Performance would be significantly higher in 2 features rather than 4096 features.

2.4 PCA Exploration [No Points]¶

Note The accuracy can differ from the TA solution and this section is not graded.

Emotion Dataset [No Points]¶

Now you will use PCA on an actual real-world dataset. We will use your implementation of PCA function to reduce the dataset with 99% retained variance and use it to obtain the reduced features. On the reduced dataset, we will use logistic and linear regression to compare results between PCA and non-PCA datasets. Run the following cells to see how PCA works on regression and classification tasks.

The first dataset we will use is an emotion dataset made up of grayscale images of human faces faces that are visibly happy and visibly sad. Note how Accuracy increases after reducing the number of features used.

Now we will explore sklearn's Diabetes dataset using PCA dimensionality reduction and regression. Notice the RMSE score reduction after we apply PCA.

Q3 Polynomial regression and regularization [80pts: 50pts + 20pts Bonus for Undergrads + 10pts Bonus for All] **[P]** | **[W]**¶

3.1 Regression and regularization implementations [50pts: 30 pts + 20 pts bonus for CS 4641] **[P]**¶

We have three methods to fit linear and ridge regression models: 1) closed form solution; 2) gradient descent (GD); 3) stochastic gradient descent (SGD). Some of the functions are bonus, see the below function list on what is required to be implemented for graduate and undergraduate students. We use the term weight in the following code. Weights and parameters ($\theta$) have the same meaning here. We used parameters ($\theta$) in the lecture slides.

In the regression.py file, complete the Regression class by implementing the listed functions below. We have provided the Loss function, $L$, associated with the GD and SGD function for Linear and Ridge Regression for deriving the gradient update.

• rmse
• construct_polynomial_feats
• predict
• linear_fit_closed: You should use np.linalg.pinv in this function

• linear_fit_GD (bonus for undergrad, required for grad): $$L_{\text{linear, GD}}(\theta) = \dfrac{1}{2N} \sum_{i=0}^{N} [y_i - \hat{y}_i(\theta)]^2 \quad\quad y_i = \text{label}, \, \hat{y}_i(\theta) = \text{prediction}$$

• linear_fit_SGD (bonus for undergrad, required for grad): $$L_{\text{linear, SGD}}(\theta) = \dfrac{1}{2} [y_i - \hat{y}_i(\theta)]^2 \quad\quad y_i = \text{label}, \, \hat{y}_i(\theta) = \text{prediction}$$

• ridge_fit_closed: You should adjust your I matrix to handle the bias term differently than the rest of the terms

• ridge_fit_GD (bonus for undergrad, required for grad): $$L_{\text{ridge, GD}}(\theta) = L_{\text{linear, GD}}(\theta) + \dfrac{c_{\lambda}}{2N}\theta^T\theta$$

• ridge_fit_SGD (bonus for undergrad, required for grad):

$$L_{\text{ridge, SGD}}(\theta) = L_{\text{linear, SGD}}(\theta) + \dfrac{c_{\lambda}}{2N}\theta^T\theta$$

• ridge_cross_validation: Use ridge_fit_closed for this function

IMPORTANT NOTE:

• Use your RMSE function to calculate actual loss when coding GD and SGD, but use the loss listed above to derive the gradient update.

The points for each function is in the Deliverables and Points Distribution section.

3.1.1 Local Tests for Helper Regression Functions [No Points]¶

You may test your implementation of the functions contained in regression.py in the cell below. Feel free to comment out tests for functions that have not been completed yet. See Using the Local Tests for more details.

3.1.2 Local Tests for Linear Regression Functions [No Points]¶

You may test your implementation of the functions contained in regression.py in the cell below. Feel free to comment out tests for functions that have not been completed yet. See Using the Local Tests for more details.

3.1.3 Local Tests for Ridge Regression Functions [No Points]¶

You may test your implementation of the functions contained in regression.py in the cell below. Feel free to comment out tests for functions that have not been completed yet. See Using the Local Tests for more details.

3.1.4 Local Tests for Gradient Descent and SGD (Bonus for Undergrad Tests) [No Points]¶

You may test your implementation of the functions contained in regression.py in the cell below. Feel free to comment out tests for functions that have not been completed yet. See Using the Local Tests for more details.

3.2 About RMSE [3 pts] **[W]**¶

What is a good RMSE value?

If we normalize our labels such that the true labels $y$ and the model outputs $\hat{y}$ can only be between 0 and 1, what does it mean when the RMSE = 1? Please provide an example with your explanation.

**ANSWER:** ...

Having an RMSE of 1 indicates that the model is performing terribly. The RMSE value should be closer to 0 because this indicates that the model is making less errors while a higher RMSE value indicates a larger error in prediction.

3.3 Testing: General Functions and Linear Regression [5 pts] **[W]**¶

In this section. we will test the performance of the linear regression. As long as your test RMSE score is close to the TA's answer (TA's answer $\pm 0.05$), you can get full points. Let's first construct a dataset for polynomial regression.

In this case, we construct the polynomial features up to degree 5. Each data sample consists of two features $[a,b]$. We compute the polynomial features of both $a$ and $b$ in order to yield the vectors $[1,a,a^2,a^3, \ldots, a^{\text{degree}}]$ and $[1,b,b^2,b^3, \ldots, b^{\text{degree}}]$. We train our model with the cartesian product of these polynomial features. The cartesian product generates a new feature vector consisting of all polynomial combinations of the features with degree less than or equal to the specified degree.

For example, if degree = 2, we will have the polynomial features $[1,a,a^2]$ and $[1,b,b^2]$ for the datapoint $[a,b]$. The cartesian product of these two vectors will be $[1,a,b,ab,a^2,b^2]$. We do not generate $a^3$ and $b^3$ since their degree is greater than 2 (specified degree).

In the figure above, the red curve is the true fuction we want to learn, while the blue dots are the noisy data points. The data points are generated by $Y=X\theta+\epsilon$, where $\epsilon_i \sim N(0,1)$ are i.i.d. generated noise.

Now let's split the data into two parts, the training set and testing set. The yellow dots are for training, while the black dots are for testing.

Now let us train our model using the training set and see how our model performs on the testing set. Observe the red line, which is our model's learned function.

HINT: If your RMSE is off, make sure to follow the instruction given for linear_fit_closed in the list of functions to implement above.

Now let's use our linear gradient descent function with the same setup. Observe that the trendline is now less optimal, and our RMSE decreased. Do not be alarmed.

We must tune our epochs and learning_rate. As we tune these parameters our trendline will approach the trendline generated by the linear closed form solution. Observe how we slowly tune (increase) the epochs and learning_rate below to create a better model.

Note that the closed form solution will always give the most optimal/overfit results. We cannot outperform the closed form solution with GD. We can only approach closed forms level of optimality/overfitness. We leave the reasoning behind this as an exercise to the reader.

And what if we just use the first 10 data points to train?

Did you see a worse performance? Let's take a closer look at what we have learned.

3.4 Testing: Testing ridge regression [5 pts] **[W]**¶

Now let's try ridge regression. Like before, undergraduate students need to implement the closed form, and graduate students need to implement all three methods. We will call the prediction function from linear regression part. As long as your test RMSE score is close to the TA's answer (TA's answer $\pm 0.05$), you can get full points.

Again, let's see what we have learned. You only need to run the cell corresponding to your specific implementation.

HINT: Make sure to follow the instruction given for ridge_fit_closed in the list of functions to implement above.

3.5 Cross validation [7 pts] **[W]**¶

Let's use Cross Validation to search for the best value for c_lambda in ridge regression.

Imagine we have a dataset of 10 points [1,2,3,4,5,6,7,8,9,10] and we want to do 5-fold cross validation.

• The first iteration we would train with [3,4,5,6,7,8,9,10] and test (validate) with [1,2]
• The second iteration we would train with [1,2,5,6,7,8,9,10] and test (validate) with [3,4]
• The third iteration we would train with [1,2,3,4,7,8,9,10] and test (validate) with [5,6]
• The fourth iteration we would train with [1,2,3,4,5,6,9,10] and test (validate) with [7,8]
• The fifth iteration we would train with [1,2,3,4,5,6,7,8] and test (validate) with [9,10]

We provided a list of possible values for $\lambda$, and you will use them in cross validation. For cross validation, use 10-fold method and only use it for your training data (you already have the train_indices to get training data). For the training data, split them in 10 folds which means that use 10 percent of training data for test and 90 percent for training. For each $\lambda$, you will have calculated 10 RMSE values. Compute the mean of the 10 RMSE values. Then pick the $\lambda$ with the lowest mean RMSE.

HINTS:

• np.concatenate is your friend
• Make sure to follow the instruction given for ridge_fit_closed in the list of functions to implement above.
• To use the 10-fold method, that would include looping over all the data 10 times, where we split a different 10% of the data at every iteration. So the first iteration extracts the first 10% to testing and the remaining 90% for training.The second iteration splits the second 10% of data for testing and the (different) remaining 90% for testing. If we have the array of elements 1 - 10, the second iteration would extract the number "2" because that's in the second 10% of the array.
• The hyperparameter_search function will handle averaging the errors, so don't average the errors in ridge_cross_validation. We've done this so you can see your error across every fold when using the gradescope tests.

3.6 Noisy Input Samples in Linear Regression [10 pts Bonus for All] **[W]**¶

Consider a linear model of the form: $$y(x_n,\theta) = \theta_0 + \sum_{d=1}^D\theta_dx_{nd}$$ where $x_n = (x_{n1}, \ldots, x_{nD}) \in \mathbb{R}^{D}$ and weights $\theta = (\theta_0, \ldots, \theta_D) \in \mathbb{R}^{D}$. Given the the D-dimension input sample set $x = \{ x_1, \ldots, x_n\}$ with corresponding target value $y = \{y_1, \ldots, y_n\}$, the sum-of-squares error function is: $$E_D(\theta) = \frac{1}{2}\sum_{n=1}^N\left[y(x_n,\theta)-y_n\right]^2$$

Now, suppose that Gaussian noise $\epsilon_n \in \mathbb{R}^{D}$ is added independently to each of the input sample $x_n$ to generate a new sample set $x'= \{x_1+\epsilon_1, \ldots, x_n+\epsilon_n\}$. Here, $\epsilon_{ni}$ (an entry of $\epsilon_n$) has zero mean and variance $\sigma^2$. For each sample $x_n$, let $x_n' = (x_{n1} + \epsilon_{n1}, \ldots, x_{nD} + \epsilon_{nd})$, where $n$ and $d$ is independent across both $n$ and $d$ indices.

1. (3pts) Show that $y(x_n',\theta) = y(x_n, \theta) + \sum^D_{d=1}\theta_d\epsilon_{nd}$

2. (7pts) Assume the sum-of-squares error function of the noise sample set $x'= \{x_1+\epsilon_1, \ldots, x_n+\epsilon_n\}$ is $E_D(\theta)'$. Prove the expectation of $E_D(\theta)'$ is equivalent to the sum-of-squares error $E_D(\theta)$ for noise-free input samples with the addition of a weight-decay regularization term (e.g. $\ell_2$ norm) , in which the bias parameter $\theta_0$ is omitted from the regularizer. In other words, show that $$E[E_D(\theta)'] = E_D(\theta) + \text{Regularizer}.$$

N.B. You should be incorporating your solution from the first part of this problem into the given sum of squares equation for the second part.

HINT:

• During the class, we have discussed how to solve for the weight $\theta$ for ridge regression, the function looks like this: $$E(\theta)=\frac{1}{N}\sum_{i=1}^N\left[ y(x_i,\theta)-y_i \right]^2+\frac{\lambda}{N}\sum_{i=1}^d |\theta_i|^2$$ where the first term is the sum-of-squares error and the second term is the regularization term. N is the number of samples. In this question, we use another form of the ridge regression, which is: $$E(\theta)=\frac{1}{2}\sum_{i=1}^N\left[y(x_i,\theta)-y_i \right]^2+\frac{\lambda}{2}\sum_{i=1}^d |\theta_i|^2$$

• For the Gaussian noise $\epsilon_n$, we have $E[\epsilon_n]=0$

• Assume the noise $\epsilon = (\epsilon_1,..., \epsilon_n)$ are independent to each other, we have $$E[\epsilon_n\epsilon_m]=\left\{ \begin{array}{rcl} \sigma^2 & & m = n\\ 0 & & m \neq n\\ \end{array} \right.$$

1. Answer: ...

1. Answer: ...

Q4: Naive Bayes and Logistic Regression [35pts] **[P]** | **[W]**¶

In Bayesian classification, we're interested in finding the probability of a label given some observed feature vector $x = [x_{1}, \ldots, x_{d}]$, which we can write as $P(y~|~{ x_{1}, \ldots, x_{d}})$. Bayes's theorem tells us how to express this in terms of quantities we can compute more directly:

$$P(y~|~{ x_{1}, \ldots, x_{d}}) = \frac{P({ x_{1}, \ldots, x_{d}}~|~y)P(y)}{P({ x_{1}, \ldots, x_{d}})}$$

The main assumption in Naive Bayes is that, given the label, the observed features are conditionally independent i.e.

$$P({ x_{1}, \ldots, x_{d}}~|~y) = P({x_{1}}~|~y) \times \ldots \times P({x_{d}}~|~y)$$

Therefore, we can rewrite Bayes rule as

$$P(y~|~{ x_{1}, \ldots, x_{d}}) = \frac{P({x_{1}}~|~y) \times \ldots \times P({x_{d}}~|~y)P(y)}{P({ x_{1}, \ldots, x_{d}})}$$

Training Naive Bayes¶

One way to train a Naive Bayes classifier is done using frequentist approach to calculate probability, which is simply going over the training data and calculating the frequency of different observations in the training set given different labels. For example,
$$P({x_{1}=i}~|~y=j) = \frac{P({x_{1}=i}, y=j)}{P(y=j)} = \frac{\text{Number of times in training data } x_{1}=i \text{ and } y=j }{\text{Total number of times in training data } y=j}$$

Testing Naive Bayes¶

During the testing phase, we try to estimate the probability of a label given an observed feature vector. We combine the probabilities computed from training data to estimate the probability of a given label. For example, if we are trying to decide between two labels $y_{1}$ and $y_{2}$, then we compute the ratio of the posterior probabilities for each label:

$$\frac{P(y_{1}~|~ x_{1}, \ldots, x_{d})}{P(y_2~|~x_{1},.., x_{d})} = \frac{P(x_{1}, \ldots, x_{d}~|~y_{1})}{P(x_{1}, \ldots, x_{d}~|~y_{2})}\frac{P(y_1)}{P(y_2)}= \frac{P({x_{1}}~|~y_{1}) \times \ldots \times P({x_{d}}~|~y_{1})P(y_{1})}{P({x_{1}}~|~y_{2}) \times \ldots \times P({x_{d}}~|~y_{2})P(y_{2})}$$

All we need now is to compute $P(x_{1}|y_{i}), \ldots, P(x_{d}~|~y_i)$ and $P(y_{i})$ for each label by plugging in the numbers we got during training. The label with the higher posterior probabilities is the one that is selected.

4.1 Llama Breed Problem using Naive Bayes [5pts] [W]¶

Above are images of two different breeds of llamas – the Suri and the Wooly. The difference between these two breeds is subtle, as these two breeds are often mixed up. However the Suri Llama is vastly more valuable than the Wooly llama. You devise a way to determine with some confidence, which is which – without the need for expensive genetic testing.

You look at four key features of the llama: {curly hair, over 14 inch tail, over 400 pounds, extremely shy}.

You only have 6 randomly chosen llamas to work with, and their breed as the ground truth. You record the data as vectors with the entry 1 if true and 0 if false. For example a llama with vector {1,1,0,1} would have curly hair, a tail over 14 inches, be less than 400 pounds, and be extremely shy.

The Suri Llamas yield the following data: {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 1, 1, 1}, {0, 0, 0, 1}

The Wooly Llamas yield the following data: {0, 0, 1, 0}, {1, 1, 0, 0}.

Now is the time to test your method!

You see a new llama you are interested in that has curly hair, does not have a tail over 14 inches, is less than 400 pounds, and is not shy.

Using Naive Bayes, is this a Suri or a Wooly Llama?

NOTE: We expect students to show their work (Naive Bayes calculations) and not just the final answer.

Answer: ...

Wooly:

Curly Hair: 1/2 Tail over 14 inches: 1/2 Over 400 pounds = 1/2 Extremly Shy: 0

Suri Llama:

Curly Hair: 3/4 Tail Over 14 Inches: 1/2 Over 400 Pounds: 1/2 Extremly Shy: 1/2

P(Wooly) = 1,0,0,0 = 1/2 4/2 1/2 1 1/3 = 1 / 24 P(Suri) = 1,0,0,0 = 3/4 1/2 1/2 1/2 2/3 = 1 / 16

P(Suri) / P(Wooly) = (1/16) / (1/24) = 1.5

This proves that it is more likely to be a Suri Llama

4.2 News Data Sentiment Classification via Logistic Regression [30pts] **[P]**¶

This dataset contains the sentiments for financial news headlines from the perspective of a retail investor. The sentiment of news has 3 classes, negative, positive and neutral. In this problem, we only use the negative (class label = 0) and positive (class label = 1) classes for binary logistic regression. For data preprocessing, we remove the duplicate headlines and remove the neutral class to get 1967 unique news headlines. Then we randomly split the 1967 headlines into training set and evaluation set with 8:2 ratio. We use the training set to fit a binary logistic regression model.

The code which is provided loads the documents, preprocess the data, builds a “bag of words” representation of each document. Your task is to complete the missing portions of the code in logisticRegression.py to determine whether a news headline is negative or positive.

In logistic_regression.py file, complete the following functions:

• sigmoid: transform $s = x\theta$ to probability of being positive using sigmoid function, which is $\frac{1}{1+e^{-s}}$.
• bias_augment: augment $x$ with 1's to account for bias term in $\theta$
• predict_probs: predicts the probability of positive label $P(y = 1 | x)$
• predict_labels: predicts labels
• loss: calculates binary cross-entropy loss
• gradient: calculate the gradient of the loss function with respect to the parameters $\theta$.
• accuracy: calculate the accuracy of predictions
• evaluate: gives loss and accuracy for a given set of points
• fit: fit the logistic regression model on the training data.

Logistic Regression Overview:¶

1. In logistic regression, we model the conditional probability using parameters $\theta$, which includes a bias term b. $$p(y_i=1\, |\, x_i;\theta )\, =\, {h}_{\theta }(x_i) = {\sigma}(x\theta)$$ $$p(y_i=0\, |\, x_i;\theta )\, =\, {1-h}_{\theta }(x_i)$$

where $\sigma(\cdot)$ is the sigmoid function as follows: $$\sigma(s) = \frac{1}{1+e^{-s}}$$

1. The conditional probabilities of the positive class $(y=1)$ and the negative class $(y=0)$ of the sample $x_i$ attributes are combined into one equation as follows:

$$p(y_i\, |\, x_i;\theta )\, =\, {({h}_{\theta }(x_i))}^{y_i}\, {(1-{h}_{\theta }(x_i))}^{1-y_i}$$

1. Assuming that the samples are independent of each other, the likelihood of the entire dataset is the product of the probabilities of all samples. We use maximum likehood estimation to estimate the model parameters $\theta$. The negative log likelihood (scaled by the dataset size $N$) is given by: $$\mathcal{L}(\theta \mid X, Y)\, \, =-\frac{1}{N}\, \sum ^{N}_{i=1} {{y}_i}\log{h_\theta(x_i)}+\, {(1-{y}_i)}\log(1-h_\theta({x}_i))$$

where:

$N =$ number of training samples
$x_i =$ bag of words features of the i-th training sample
$y_i =$ label of the i-th training sample

Note that this will be our model's loss function

1. Then calculate the gradient $\triangledown_\theta\mathcal{L}$ and use gradient descent to optimize the loss function: $$\theta_{t+1} = \theta_{t} - \eta \cdot \triangledown_\theta\mathcal{L}(\theta_t \mid X, Y)$$

where $\eta$ is the learning rate and the gradient $\triangledown_\theta\mathcal{L}$ is given by:

$$\triangledown_\theta \mathcal{L}(\theta \mid X, Y) = \frac{1}{N} \sum_{i=1}^{N} x_{i}^{\top} \left( h_{\theta}(x_i) - y_i \right)$$

4.2.1 Local Tests for Logistic Regression [No Points]¶

You may test your implementation of the functions contained in logistic_regression.py in the cell below. Feel free to comment out tests for functions that have not been completed yet. See Using the Local Tests for more details.

4.2.2 Logistic Regression Model Training [No Points]¶

Fit the model to the training data. Feel free to try different learning rates lr and number of epochs to achieve >80% test accuracy.

4.2.3 Logistic Regression Model Evaluation [No Points]¶

Evaluate the model on the test dataset

Plotting the loss function on the training data and the test data for every 100th epoch

Plotting the accuracy function on the training data and the test data for each epoch

Check out sample evaluations from the test set.

Q5: Noise in PCA and Linear Regression [15pts] **[W]**¶

Both PCA and least squares regression can be viewed as algorithms for inferring (linear) relationships among data variables. In this part of the assignment, you will develop some intuition for the differences between these two approaches and develop an understanding of the settings that are better suited to using PCA or better suited to using the least squares fit.

The high level bit is that PCA is useful when there is a set of latent (hidden/underlying) variables, and all the coordinates of your data are linear combinations (plus noise) of those variables. The least squares fit is useful when you have direct access to the independent variables, so any noisy coordinates are linear combinations (plus noise) of known variables.

5.1 Slope Functions [5 pts] **[W]**¶

In the following cell, complete the following:

1. pca_slope: For this function, assume that $X$ is the first feature and $y$ is the second feature for the data. Write a function, that takes in the first feature vector $X$ and the second feature vector $y$. Stack these two feature vectors into a single N x 2 matrix and use this to determine the first principal component vector of this dataset. Be careful of how you are stacking the two vectors. You can check the output by printing it which should help you debug. Finally, return the slope of this first component. You should use the PCA implementation from Q2.
   
   

2. lr_slope: Write a function that takes $X$ and $y$ and returns the slope of the least squares fit. You should use the Linear Regression implementation from Q3 but do not use any kind of regularization. Think about how weight could relate to slope.

In later subparts, we consider the case where our data consists of noisy measurements of $x$ and $y$. For each part, we will evaluate the quality of the relationship recovered by PCA, and that recovered by standard least squares regression.

As a reminder, least squares regression minimizes the squared error of the dependent variable from its prediction. Namely, given $(x_i, y_i)$ pairs, least squares returns the line $l(x)$ that minimizes $\sum_i (y_i − l(x_i))^2$.

We will consider a simple example with two variables, $x$ and $y$, where the true relationship between the variables is $y = 4x$. Our goal is to recover this relationship—namely, recover the coefficient “4”. We set $X = [0, .02, .04, .06, \ldots, 1]$ and $y = 4x$. Make sure both functions return 4.